﻿#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
//本代码的目的是学习与练习AVL树的插入逻辑（重点在于旋转）

//定义AVLTree的节点
template<class K, class V>
struct AVLTNode
{
	AVLTNode(pair<K, V> kv)
		:_kv(kv)
	{
	}
	pair<K, V> _kv;
	AVLTNode<K, V>* _left = nullptr;
	AVLTNode<K, V>* _right = nullptr;
	AVLTNode<K, V>* _parent = nullptr;
	int _bf = 0;
};

//定义AVLTree类
template<class K, class V>
class AVLTree
{
	typedef AVLTNode<K, V> AVLTNode;
public:
	//目前不打算实现迭代器，这里的insert函数返回节点的bool吧
	bool Insert(const pair<K, V>& kv)
	{
		//当AVL树为空时
		if (_root == nullptr)
		{
			_root = new AVLTNode(kv);
			return true;
		}

		//当树不为空时
		AVLTNode* parent = nullptr;
		AVLTNode* prve = _root;
		//AVLTNode* newnode = new AVLTNode(kv);不要在未确定kv是否键值冗余的情况下申请新节点，以免内存泄漏
		//寻找符合搜索二叉树规则的插入位置
		while (prve != nullptr)
		{
			if (kv.first == prve->_kv.first)
			{
				return false;
			}
			else if (kv.first > prve->_kv.first)
			{
				parent = prve;
				prve = prve->_right;
			}
			else if (kv.first < prve->_kv.first)
			{
				parent = prve;
				prve = prve->_left;
			}
		}

		//当确定不存在键值冗余时创建新节点
		AVLTNode* newnode = new AVLTNode(kv);
		//通过parent指针链接新节点
		if (kv.first > parent->_kv.first)
		{
			parent->_right = newnode;
			newnode->_parent = parent;
			++parent->_bf;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = newnode;
			newnode->_parent = parent;
			--parent->_bf;
		}
		else//发生意外情况时，即不符合设计逻辑时，触发断言
		{
			assert(false);
		}

		//插入节点后，观察parent节点的bf值，分情况进行处理
		AVLTNode* cur = newnode;//将newnode的值赋给cur做初始值，避免后续使用造成歧义
		while (1)//这里我将循环设计为了死循环，原因是针对三种情况中，
		//0 / -2 / 2经过一次处理即可退出循环，当循环未结束时，
		//说明上次循环一定进入了1 / -1条件，而对于该种情况，
		//又要重新分三种情况讨论，当循环仍旧继续，说明该次仍进入了1 / -1条件，
		//但就算一直进入该条件，当cur == root时，也会触发if(1 / -1)的break，
		//因此，循环最终一定会停止，必定不会陷入死循环
		{
			//1.当插入后bf==0，说明此时parent的子树高度一致，无需向上调整bf
			//	退出循环即可
			if (parent->_bf == 0)
			{
				break;
			}
			//2.当插入后bf==1/-1，说明newnode的parent.bf原本为0，插入后导致子树高度发生变化（高度增加）
			//  会影响上面节点的bf，因此需要循环进行处理，以保证bf值的正确性
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
				if (parent == nullptr)//当parent为nullptr时，说明cur已经走到根节点且根据此处if判断条件，cur==1/-1，因此无需旋转，退出循环即可
				{
					break;
				}
				if (parent->_left == cur)//若left == cur，说明左子树高度加1，parent的bf--
				{
					--parent->_bf;
				}
				else if (parent->_right == cur)//若right == cur，说明右子树高度加1，parent的bf++
				{
					++parent->_bf;
				}
			}
			//3.当插入后bf==2/-2，便破坏了AVL树的规则，应使用旋转对树进行调整
			//	使用旋转后，旋转部分整体的根部bf将更新为0，则无需继续循环，退出即可
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转共分为4种情况
				//注：为什么只可以分为四种情况呢？
				//	  因为单次旋转仅需要改变两个节点的left与right
				//	  进入该条件判断时，父节点的bf==2/-2，则cur不可能为0与-2/2（若cur为这三个值，则在之前的循环便会break，因此不可能出现在此情况中）
				//    因此，cur一定为1/-1，而2 * 2 = 4
				//    
				//1.左单旋
				if (parent->_bf == 2 && cur->_bf == 1)//当parent_bf为2时，说明原为1，则说明parent的右子树高度增加，
												//即cur是parent的右子树的根，而当cur_bf==1时，说明由0更新为1，
												//则新节点位于cur的右子树，此时需要使用左单旋使树平衡
				{
					RotateL(parent);
				}
				//2.右单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				//3.左右双旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent, kv);
				}
				//4.右左双旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent, kv);
				}
				break;
			}
			//根据分析，仅可能有上述三种情况，若出现诸如-3/3等错误，直接断言即可
			else
			{
				assert(false);
			}
		}
	}
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	//测试正确性用代码
	int Height()
	{
		return _Height(_root);
	}
	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}
private:
	AVLTNode* _root = nullptr;
	//注：这里实现的四个旋转函数内部更改了parent等节点的位置，但未将这些节点地址进行更新，调用函数时需注意
	//左单旋
	void RotateL(AVLTNode* parent)
	{
		AVLTNode* cur = parent->_right;
		//首先存储父节点的上一节点地址，旋转结束后旋转部分的根仍需链接此地址
		AVLTNode* pparent = parent->_parent;
		//左单旋正式开始
		parent->_right = cur->_left;
		if (cur->_left)//注意判断cur->_left是否为空节点，小心造成解引用空指针
		{
			cur->_left->_parent = parent;//由于是三叉链，需注意更新节点中的_parent值
		}
		cur->_left = parent;
		parent->_parent = cur;//将源父节点的parent指向cur
		//处理cur节点与parent节点的bf值
		cur->_bf = 0;
		parent->_bf = 0;
		//判断pparent是否为空，若为空，则代表对根节点进行了单旋操作，
		//但parent传递的是形参，因此此时需直接更改root的值
		if (pparent == nullptr)
		{
			_root = cur;
			cur->_parent = pparent;//将根节点的_parent置空
		}
		else {
			//不光要将cur链接至pparent，还要记得更新pparent的指针
			if (pparent->_left == parent)
			{
				pparent->_left = cur;
			}
			else if (pparent->_right == parent)
			{
				pparent->_right = cur;
			}
			cur->_parent = pparent;//最终将旋转后的cur的_parent指向pparent
		}
	}
	//右单旋（与左单旋逻辑高度类似）
	void RotateR(AVLTNode* parent)
	{
		AVLTNode* cur = parent->_left;
		AVLTNode* pparent = parent->_parent;
		parent->_left = cur->_right;
		if (cur->_right)
		{
			cur->_right->_parent = parent;//更新节点中的_parent值
		}
		cur->_right = parent;
		parent->_parent = cur;//将源父节点的parent指向cur
		cur->_bf = 0;
		parent->_bf = 0;
		if (pparent == nullptr)
		{
			_root = cur;
			cur->_parent = pparent;
		}
		else {
			//不光要将cur链接至pparent，还要记得更新pparent的指针
			if (pparent->_left == parent)
			{
				pparent->_left = cur;
			}
			else if (pparent->_right == parent)
			{
				pparent->_right = cur;
			}
			cur->_parent = pparent;//最终将旋转后的cur的_parent指向pparent
		}
	}
	//左右双旋
	void RotateLR(AVLTNode* parent, const pair<K, V>& kv)//需要传参kv，用来区分两种子情况，以正确为bf赋值
	{
		AVLTNode* pparent = parent->_parent;
		AVLTNode* cur = parent->_left;
		AVLTNode* childcur = cur->_right;
		//先对cur与childcur进行左单旋（调用左单旋函数）
		RotateL(cur);
		//再对parent与cur进行右单旋（调用右单旋函数）
		RotateR(parent);
		//由于双旋函数内部复用了两单旋函数，所以已经更改了节点的bf值
		//而更改的值与双旋本应更改的值存在部分不匹配，因此，需要再次对bf赋值
		//与此同时，左右双旋可分为两种小情况（即同目录下png双旋文件示例），
		//但与此同时，还需注意h==0的特殊情况，因此，bf值的更新也需要进行区分
		if (childcur->_kv.first == kv.first)//注意h==0的特殊情况
		{
			parent->_bf = 0;
			cur->_bf = 0;
			childcur->_bf = 0;
		}
		else if (childcur->_kv.first < kv.first && parent->_kv.first > kv.first)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			childcur->_bf = 0;
		}
		else if (childcur->_kv.first > kv.first && cur->_kv.first < kv.first)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			childcur->_bf = 0;
		}
		//出现意料之外的情况时，终止程序
		else
		{
			cout << childcur->_kv.first << " " << cur->_kv.first << " " << kv.first << endl;
			assert(false);
		}
		
	}
	//右左双旋
	void RotateRL(AVLTNode* parent, const pair<K, V>& kv)
	{
		AVLTNode* pparent = parent->_parent;
		AVLTNode* cur = parent->_right;
		AVLTNode* childcur = cur->_left;
		RotateR(cur);
		RotateL(parent);
		if (childcur->_kv.first == kv.first)//注意h==0的特殊情况
		{
			parent->_bf = 0;
			cur->_bf = 0;
			childcur->_bf = 0;
		}
		else if (parent->_kv.first < kv.first && childcur->_kv.first > kv.first)
		{
			parent->_bf = 0;
			cur->_bf = 1;
			childcur = 0;
		}
		else if (childcur->_kv.first < kv.first && cur->_kv.first > kv.first)
		{
			parent->_bf = -1;
			cur->_bf = 0;
			childcur = 0;
		}
		else
		{
			cout << parent->_kv.first << " " << childcur->_kv.first << " " << cur->_kv.first << " " << kv.first << endl;
			assert(false);
		}
	}
	//中序遍历
	void _InOrder(AVLTNode* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << " ";
		_InOrder(root->_right);
	}
	//测试正确性代码
	int _Height(AVLTNode* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	bool _IsBalanceTree(AVLTNode* root)
	{
		// 空树也是AVL树 
		if (nullptr == root)
			return true;
		// 计算pRoot结点的平衡因子：即pRoot左右子树的⾼度差 
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者 
		// pRoot平衡因子的绝对值超过1，则一定不是AVL树 
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度差异常" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		// pRoot的左和右如果都是AVL树，则该树一定是AVL树 
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
};

//易错点（自己第一次尝试写时出现的错误）总结
//1.单旋函数中，不仅要将单旋部分的根节点_parent赋值为pparent，还要记得更新对应pparent的指针指向
//2.单旋函数中，cur节点的需要被移动的子树可能为空，要记得在移动之前进行判断，
//	避免因诸如"cur->_left->_parent"的问题造成解引用空指针
//3.注意判断进行单旋的树是否就是整棵AVL树，若是的话，需要更新_root的值
//4.双旋处需要注意，最终成为双旋部分根节点的childcur可能是新插入的节点，
//	即h==0的情况，因此，在判断情况时，也需对该特殊情况进行处理
